iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 29
0
自我挑戰組

學習資料結構30天系列 第 29

[Data Structure][Sort] - Quick Sort

  • 分享至 

  • xImage
  •  

前言

Quick Sort 跟 Merge Sort 一樣都是 Divide and Conquer

  • Divide and Conquer 就是將複雜問題分解成很多個簡單的問題,先解決所有的簡單的問題,再把所有簡單的問題的答案合起來作為複雜問題的答案。

    • Divide : 將n個數字分割成兩個數列分別是:比基準大的數列和比基準小的數列。
    • Conquer : 再去分割兩個數列。
    • Combine : 每個數列分割完後,最後會得到一個有序的數列。

Quick Sort

在數列中選一個作為Pivot,並讓Pivot的左邊數值都會比pivot小,且Pivot的右邊數值都會比pivot大,然後在把pivot的左邊和pivot的右邊排好。

  • 時間複雜度: O(nlogn),worst case : O(n²)
  • 實作:
public class Quick_Sort 
{
	public static void main(String[] args)
	{
		int ary[] =  {52, 99, 31, 60, 7, 46, 53};
		
		// before sort
		PrintArray(ary); 
				
		System.out.println("--------------------");
		QuickSort(ary, 0, ary.length - 1);
		        
		// after sort
		PrintArray(ary);
	}
	
	public static void QuickSort(int arr[], int left, int right) 
	{
        if(left < right) 
        { 
            int pivot = Partition(arr, left, right); 
            QuickSort(arr, left, pivot - 1); 
            QuickSort(arr, pivot + 1, right); 
        } 
    }

    public static int Partition(int arr[], int left, int right) 
    {  
    	int pivot = arr[left];
    	
        int i = left + 1; //放比基準值小的數值
        
        //從左邊到右邊,找出比基準值小的數值做交換
        for(int j = left + 1; j <= right; j++) 
        { 
            if(arr[j] <= pivot)
            { 
                Swap(arr, i, j);
                i++;
            }
        } 
        //把基準值交換到中間,讓基準值大於左邊的數,小於右邊的數
        Swap(arr, left, i - 1); 
        return i - 1; 
    } 

    public static void Swap(int arr[], int x, int y)
	{
		int temp = arr[x];
		arr[x] = arr[y];
		arr[y] = temp;
	}
	
	public static void PrintArray(int arr[])
	{
		for(int i = 0; i < arr.length; i++)
	    {
			System.out.print(arr[i] + " ");
	    }
		System.out.println();
	}
    
}

輸出結果:

52 99 31 60 7 46 53 
--------------------
7 31 46 52 53 60 99 

上一篇
[Data Structure][Sort] - Merge Sort
下一篇
[Data Structure][Search] - Binary Search
系列文
學習資料結構30天30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言